from functools import lru_cache
from typing import List
class Solution:
    def num_distinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        if m < n:  # 如果m<n,则t一定不和s的子序列相等,返回0
            return 0

        dp = [[0] * (n + 1) for _ in range(m + 1)]   # 全为0
        for i in range(m + 1):
            dp[i][n] = 1  # 空字符串是任何字符串的子序列,返回1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if s[i] == t[j]:
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
                else:
                    dp[i][j] = dp[i + 1][j]

        return dp[0][0]

    def isMatch(self, s: str, p: str) -> bool:
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        dp[0][0] = True
        for j in range(1, len(p) + 1):
            if p[j - 1] == '*' and dp[0][j - 2]:
                dp[0][j] = True
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    if s[i - 1] != p[j - 2] and p[j - 2] != '.':
                        dp[i][j] = dp[i][j - 2]
                    else:
                        dp[i][j] = dp[i][j - 2] or dp[i - 1][j] or dp[i - 1][j - 2]
        return dp[-1][-1]

    def isMatch_lru(self, s: str, p: str) -> bool:
        # 装饰器实现记忆化搜索
        @lru_cache(None)
        def recur(i, j):
            # 结束条件
            if j == len(p): return i == len(s)
            # 首字母匹配
            first_match = (len(s) > i) and (p[j] == s[i] or p[j] == '.')
            # 处理 `*`
            if len(p) >= j + 2 and p[j + 1] == '*':
                return recur(i, j + 2) or (first_match and recur(i + 1, j))
            # 处理首字母匹配
            return first_match and recur(i + 1, j + 1)

        return recur(0, 0)
    
    MAXN = 10**6 # 最大值
    INF = 10**9 # 无穷大
    flag = False # 是否已经初始化
    is_prime = [True]*(MAXN+1) # 是否是质数
    prime = [] # 质数表
    factor = [0]*(MAXN+1) # 最小质因数表
    @classmethod # 类方法
    def prepare(cls):
        cls.flag = True
        for i in range(2, cls.MAXN+1):
            if cls.is_prime[i]:
                cls.prime.append(i)
                cls.factor[i] = i
            for p in cls.prime:
                t = p*i
                if t > cls.MAXN: break
                cls.is_prime[t] = False
                cls.factor[t] = p
                if i%p == 0: break

    def splitArray(self, a: list[int]) -> int:
        if not Solution.flag:
            Solution.prepare()
        mx = max(a)
        u = [Solution.INF]*(mx+1)
        f = [0]
        for x in a:
            y = x
            tmp = Solution.INF
            while y != 1:
                d = Solution.factor[y]
                u[d] = min(u[d], f[-1])
                tmp = min(tmp, u[d]+1)
                y //= d
            f.append(tmp)
        return f[-1]

    def splitArray1(self, nums: List[int], m: int) -> int:
        # 将left初始化为数组的最大值，right初始化为数组的所有元素的和
        left, right = max(nums), sum(nums)
        # 当left<right进入循环
        while left < right:
            # 取中点
            mid = (left + right) // 2
            count = 1  # 表示子数组的数量
            total = 0  # 表示当前子数组的和
            # 遍历nums中的每一个元素
            for num in nums:
                total += num  # 将当前元素添加到子数组中
                # 检查total是否大于中点
                # 如果是，将当前子数组的total设置为num，子数组数量加一
                if total > mid:
                    total = num
                    count += 1
                    if count > m:  # 检查子数组的个数是否大于目标个数
                        break
            # 检查子数组个数是否小于等于目标
            # 将right设置为mid，否则，将left设置为mid+1
            if count <= m:
                right = mid
            else:
                left = mid + 1
        # 返回left，即m个子数组的最小可能最大值
        return left
# 测试数据
# nums = [7,2,5,10,8]
# m = 2
# x=Solution.splitArray(Solution,nums,m)
# print(x)
    def shortest_common_supersequence(self, str1, str2) -> str:
        m, n = len(str1), len(str2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    f[i][j] = f[i - 1][j - 1] + 1
                else:
                    f[i][j] = max(f[i - 1][j], f[i][j - 1])
        ans = []
        i, j = m, n
        while i or j:
            if i == 0:
                j -= 1
                ans.append(str2[j])
            elif j == 0:
                i -= 1
                ans.append(str1[i])
            else:
                if f[i][j] == f[i - 1][j]:
                    i -= 1
                    ans.append(str1[i])
                elif f[i][j] == f[i][j - 1]:
                    j -= 1
                    ans.append(str2[j])
                else:
                    i, j = i - 1, j - 1
                    ans.append(str1[i])
        return "".join(ans[::-1])